<!DOCTYPE html
  PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd">
<!-- saved from url=(0014)about:internet -->
<html xmlns:MSHelp="http://www.microsoft.com/MSHelp/" lang="en-us" xml:lang="en-us"><head><meta http-equiv="Content-Type" content="text/html; charset=UTF-8">

<meta name="DC.Type" content="topic">
<meta name="DC.Title" content="Cook Until Done: parallel_do">
<meta name="DC.subject" content="Cook Until Done: parallel_do">
<meta name="keywords" content="Cook Until Done: parallel_do">
<meta name="DC.Relation" scheme="URI" content="../tbb_userguide/Parallelizing_Complex_Loops.htm">
<meta name="DC.Format" content="XHTML">
<meta name="DC.Identifier" content="tutorial_Cook_Until_Done_parallel_do">
<link rel="stylesheet" type="text/css" href="../intel_css_styles.css">
<title>Cook Until Done: parallel_do</title>
<xml>
<MSHelp:Attr Name="DocSet" Value="Intel"></MSHelp:Attr>
<MSHelp:Attr Name="Locale" Value="kbEnglish"></MSHelp:Attr>
<MSHelp:Attr Name="TopicType" Value="kbReference"></MSHelp:Attr>
</xml>
</head>
<body id="tutorial_Cook_Until_Done_parallel_do">
 <!-- ==============(Start:NavScript)================= -->
 <script src="..\NavScript.js" language="JavaScript1.2" type="text/javascript"></script>
 <script language="JavaScript1.2" type="text/javascript">WriteNavLink(1);</script>
 <!-- ==============(End:NavScript)================= -->
<a name="tutorial_Cook_Until_Done_parallel_do"><!-- --></a>

 
  <h1 class="topictitle1">Cook Until Done: parallel_do</h1>
 
  
  <div>
	 <p>For some loops, the end of the iteration space is not known in advance,
		or the loop body may add more iterations to do before the loop exits. You can
		deal with both situations using the template class 
  <span class="option">tbb::parallel_do</span>.
  </p>

  <p>A linked list is an example of an iteration space that is not known in
	 advance. In parallel programming, it is usually better to use dynamic arrays
	 instead of linked lists, because accessing items in a linked list is inherently
	 serial. But if you are limited to linked lists, the items can be safely
	 processed in parallel, and processing each item takes at least a few thousand
	 instructions, you can use 
	 <samp class="codeph">parallel_do</samp> to gain some parallelism. 
  </p>

  <p>For example, consider the following serial code:
  </p>

  <pre>void SerialApplyFooToList( const std::list&lt;Item&gt;&amp; list ) {
    for( std::list&lt;Item&gt;::const_iterator i=list.begin() i!=list.end(); ++i ) 
        Foo(*i);
}</pre>
  <p>If 
	 <samp class="codeph">Foo</samp> takes at least a few thousand instructions to run, you
	 can get parallel speedup by converting the loop to use 
	 <samp class="codeph">parallel_do</samp>. To do so, define an object with a 
	 <samp class="codeph">const</samp> qualified 
	 <samp class="codeph">operator()</samp>. This is similar to a C++ function object from
	 the C++ standard header 
	 <samp class="codeph">&lt;functional&gt;</samp>, except that 
	 <samp class="codeph">operator()</samp> must be 
	 <samp class="codeph">const</samp>.
  </p>

  <pre>class ApplyFoo {
public:
    void operator()( Item&amp; item ) const {
        Foo(item);
    }
};</pre>
  <p>The parallel form of 
	 <samp class="codeph">SerialApplyFooToList</samp> is as follows:
  </p>

  <pre>void ParallelApplyFooToList( const std::list&lt;Item&gt;&amp; list ) {
    parallel_do( list.begin(), list.end(), ApplyFoo() ); 
}</pre>
  <p>An invocation of 
	 <samp class="codeph">parallel_do</samp> never causes two threads to act on an input
	 iterator concurrently. Thus typical definitions of input iterators for
	 sequential programs work correctly. This convenience makes 
	 <samp class="codeph">parallel_do</samp> unscalable, because the fetching of work is
	 serial. But in many situations, you still get useful speedup over doing things
	 sequentially.
  </p>

  <p>There are two ways that 
	 <samp class="codeph">parallel_do</samp> can acquire work scalably. 
  </p>
 
  <ul type="disc">
	 <li>
		<p>The iterators can be random-access iterators.
		</p>

	 </li>

	 <li>
		<p>The body argument to 
		  <samp class="codeph">parallel_do</samp>, if it takes a second argument 
		  <em>feeder</em> of type 
		  <samp class="codeph">parallel_do&lt;Item&gt;&amp;</samp>, can add more work by
		  calling 
		  <samp class="codeph"><em>feeder</em>.add(<em>item</em>)</samp>. For example, suppose
		  processing a node in a tree is a prerequisite to processing its descendants.
		  With 
		  <samp class="codeph">parallel_do</samp>, after processing a node, you could use 
		  <samp class="codeph"><var>feeder</var>.add</samp> to add the descendant
		  nodes. The instance of 
		  <samp class="codeph">parallel_do</samp> does not terminate until all items have
		  been processed. 
		</p>

	 </li>

  </ul>

  <div class="section"><h2 class="sectiontitle">Code Sample</h2>
	 
	 <p>The directory 
		<samp class="codeph">examples/parallel_do/parallel_preorder</samp> contains a small
		application that uses 
		<samp class="codeph">parallel_do</samp> to perform parallel preorder traversal of an
		acyclic directed graph. The example shows how 
		<samp class="codeph">parallel_do_feeder</samp> can be used to add more work.
	 </p>

  </div>

  </div>


<div class="familylinks">
<div class="parentlink"><strong>Parent topic:</strong>&nbsp;<a href="../tbb_userguide/Parallelizing_Complex_Loops.htm">Parallelizing Complex Loops</a></div>
</div>
<div></div>

</body>
</html>
